class Solution {
    typedef pair<string, int> PSI;

    struct Com
    {
        bool operator()(PSI a, PSI b)
        {
            if (a.second == b.second)
                return a.first < b.first;
            return a.second > b.second;
        }
    };
public:
    vector<string> topKFrequent(vector<string>& words, int k) {
        unordered_map<string, int> hash;
        for (auto& str : words)
            hash[str]++;

        priority_queue<PSI, vector<PSI>, Com> heap;
        for (auto x : hash)
        {
            heap.push(x);
            if (heap.size() > k)
                heap.pop();
        }

        vector<string> ret(k);
        for (int i = k - 1; i >= 0; i--)
        {
            ret[i] = heap.top().first;
            heap.pop();
        }

        return ret;
    }
};